// @题目描述：
// 给你两棵二叉树： root1 和 root2 。想象一下，当你将其中一棵覆盖到另一棵之上时，
// 两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。
// 合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
// 返回合并后的二叉树。
// 注意: 合并过程必须从两个树的根节点开始。

// @题目链接：https://leetcode.cn/problems/merge-two-binary-trees

// 深度优先 （O(min(m,n))，O(min(m,n))）
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 相同位置其中一个节点为空的情况
        if(root1 == nullptr)    return root2;
        if(root2 == nullptr)    return root1;
        // 两个节点均不为空，则值累加到root1，这可以有效的降低复杂度
	//想一想为什么
        root1->val+= root2->val;
        // 递归的处理左右孩子
        root1->left = mergeTrees(root1->left,root2->left);
        root1->right = mergeTrees(root1->right,root2->right);
        return root1;
    }
};
// 深度优先2
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr)    return root2;
        if(root2 == nullptr)    return root1;
        // 分别使用两个栈进行两个原始树的先序遍历
        stack<TreeNode*>st1,st2;
        st1.push(root1);
        st2.push(root2);
        // 栈均不为空才做加和，否则孩子直接赋值
        // 结果树保存在原始的root1中
        while(!st1.empty() && !st2.empty()){
            TreeNode* node1 = st1.top();
            TreeNode* node2 = st2.top();
            st1.pop();
            st2.pop();
            //合并计算 
            node1->val += node2->val;
            if(node1->right!=nullptr && node2->right!=nullptr){
                st1.push(node1->right);
                st2.push(node2->right);
            }else{
                // 如果root1的孩子为空，则root2的孩子就是root的孩子
                if(node1->right == nullptr)
                    node1->right = node2->right;
            }
            if(node1->left!=nullptr && node2->left!=nullptr){
                st1.push(node1->left);
                st2.push(node2->left);
            }else{
                // 如果root1的孩子为空，则root2的孩子就是root的孩子
                if(node1->left == nullptr)
                    node1->left = node2->left;
            }
        }
        return root1;
    }
};


// 广度优先（O(min(m,n))，O(min(m,n))）
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 其中一个树节点为空的情况
        if(root1 == nullptr)    return root2;
        if(root2 == nullptr)    return root1;
        // 三个队列辅助存储广度遍历序列
        // que对应新构建的树，que1和que2对应两个原始树
        queue<TreeNode*> que,que1,que2;
        // 构造新的树根
        TreeNode* root = new TreeNode(root1->val + root2->val);
        // 三个树的根节点入栈
        que.push(root);
        que1.push(root1);
        que2.push(root2);
        // 当两个原始树均不为空才进行广度遍历，否则就可以直接跳出赋值
        // 当一个原始树节点的孩子为空，则新树节点只与另一个树有关
        // 这样可以节省计算时间和空间
        while(!que1.empty() && !que2.empty()){
            TreeNode* node = que.front();
            TreeNode* node1 = que1.front();
            TreeNode* node2 = que2.front();
            que.pop();que1.pop();que2.pop();
            auto left1 = node1->left,left2 = node2->left,
                right1 = node1->right,right2 = node2->right;
            // 左孩子的处理
            if(left1 != nullptr || left2 != nullptr){
                if(left1!=nullptr && left2!=nullptr){
                    TreeNode* left = new TreeNode(left1->val + left2->val);
                    node -> left = left;
                    que.push(left);
                    que1.push(left1);
                    que2.push(left2);
                }
                else if(left1 != nullptr){
                    // 注意把握类似代码
                    node->left = left1;
                }else{
                    node->left = left2;
                }
            }
            // 右孩子处理
            if(right1!=nullptr || right2!=nullptr){
                if(right1!=nullptr&&right2!=nullptr){
                    TreeNode* right = new TreeNode(right1->val+right2->val);
                    node->right = right;
                    que.push(right);
                    que1.push(right1);
                    que2.push(right2);
                }
                else if(right1!=nullptr)
                    node->right = right1;
                else node->right = right2;
            }
        }
        return root;
    }
};